/**
 * Created by L.jp
 * Description:你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。
 * 给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
 * User: 86189
 * Date: 2022-09-04
 * Time: 17:33
 */
public class Solution {
    public int rob (int[] nums) {
        int n= nums.length;
        if(n==1){
            return nums[0];
        }
        //初始化,dp[i]表示数组长度为i时，最多可以偷的金额
        int[] dp=new int[n+1];
        //长度为1，只有一家可以偷
        dp[1]=nums[0];
        for(int i=2;i<=n;i++){
            //i表示长度，如果是下标的话要-1
            //每一家都可以选择偷或者不偷，如果偷了这家，那么上一家就不能偷，只能偷上上家，dp[i]=dp[i-2]+nums[i-1]
            // 如果不偷这家，那么偷的最多金额就看在上一家累计偷的最多金额，dp[i]=dp[i-1]
            //两者取最大值
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[n];
    }

}
